package com.lwg.datastructure.dynamicPrograming.stockProblem;

/**
 * @FileName: StockProblem2.java
 * @Description: 买卖股票问题1
 * @author: 李炜光
 * @slogan:
 * @Date: 2022/3/8 0008
 */
/*
    定义数组 dp[i][0/1] 表示今天持股或者没持股
    在第一天时没持股为dp[0][0]=0  持股 dp[0][1]=-price[0];
    1.  dp[i][0] 今天没持股
    1.1 昨天没持股 dp[i-1][0]
    1.2 昨天持股，今天卖出 dp[i-1][1]+price[i]
    2.  dp[i][1] 今天持股
    2.1  昨天没持股，今天买入dp[i-1][0]-price[i]  此处是与1不同的地方，因为1如果今天持股了，表明是第一次买入股票，所以是-price[i]
         而本问题则是今天持股了，前几天可能已经有买卖过股票了 存在利润了所以用dp[i-1][0]-price[i]
    2.2  昨天持股了，今天没买入 即dp[i][1]=dp[i-1][1]
 */
public class StockProblem2 {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        int dp[][] = new int[length + 1][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
        }
        return dp[length-1][0];
    }
}